package com.TheEndWork.eleventhDay;

import java.util.*;

/**
 * @authoer zsj
 * @date 2022/6/2 12:27
 * <p>
 * 回溯法和递归
 * 1确定递归函数的参数和返回值
 * 2确定递归的终止条件
 * 3单层递归逻辑
 */

/*
回溯模板
void backtracking(参数) {
 if (终⽌条件) {
 存放结果;
 return;
 }
 for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
 处理节点;
 backtracking(路径，选择列表); // 递归
 回溯，撤销处理结果
 }
}
 */
public class alg {

    /**
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     */
    public List<List<Integer>> permute(int[] nums) {
        //先定义一共结果集用来返回
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        //开始回溯搜索并且将结果记录到结果集result中去
        backtracking(nums, temp, result);
        return result;
    }

    /**
     * 递归函数
     *
     * @param nums   传入初始数组
     * @param temp   结果
     * @param result 结果集
     */
    private void backtracking(int[] nums, List<Integer> temp, List<List<Integer>> result) {
        //递归函数的结束条件   因为要返回一个数字的全排列，我们每次找到一个结果的长度一定是=传入数组的长度的
        if (nums.length == temp.size()) {
            //到这里说明找到一个结果，将他加入结果集中
            result.add(new ArrayList<>(temp));
            return;
        }
        //没有找到结果，就需要遍历整个数组的数字进行累加
        //并且我们之前遍历过的结果中不能出现相同的数字
        for (int i = 0; i < nums.length; i++) {
            //必须判断当前数字是没有在之前的结果中出现过的
            if (!temp.contains(nums[i])) {
                //遍历一次我们加一个数字
                temp.add(nums[i]);
                //然后回溯去判断是否拿到结果
                backtracking(nums, temp, result);
                //要回溯前一个节点
                temp.remove(temp.size() - 1);
            }
        }
    }

    public List<List<Integer>> permute2(int[] nums) {
        //先定义一共结果集用来返回
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        //开始回溯搜索并且将结果记录到结果集result中去
        backtracking2(nums, temp, result, visited);
        return result;
    }

    /**
     * @param nums
     * @param temp
     * @param result
     * @param visited
     */
    private void backtracking2(int[] nums, List<Integer> temp, List<List<Integer>> result, boolean[] visited) {
        if (nums.length == temp.size()) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp.add(nums[i]);
                //递归
                backtracking2(nums, temp, result, visited);
                //回溯
                temp.remove(temp.size() - 1);
                visited[i] = false;
            }
        }
    }


    /**
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * 你可以按 任何顺序 返回答案。
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<Integer> box = new ArrayDeque<>();
        //注意组合是无序的
        if (k <= 0 || n < k) return ans;
        bt(n, k, 1, ans, box);
        return ans;
    }

    /**
     * @param n     最大范围
     * @param k     组合个数
     * @param begin 开始的数字
     * @param ans   结果集
     * @param box   添加到结果集中的结果
     */
    private void bt(int n, int k, int begin, List<List<Integer>> ans, Deque<Integer> box) {
        //如果当前结果的长度已经等于了我们要的组合个数
        //我们要把他加入到结果集中去
        if (box.size() == k) {
            ans.add(new ArrayList<>(box));
            return;
        }
        //一开始的begin一定会=1
        //优化剪枝  因为 如果你后面要遍历的数字已经小于了组合个数的话，就不需要往下遍历了
        //i <= n - (k - path.size()) + 1;
        for (int i = begin; i <= n - (k - box.size()) + 1; i++) {
            box.addLast(i);
            //让每次循环得到的结果都不一样,不能有重复的元素
            bt(n, k, i + 1, ans, box);
            box.removeLast();
        }
    }


    /**
     * 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
     * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
     */
    public List<String> letterCasePermutation(String s) {
        //定义结果集
        List<String> result = new ArrayList<>();
        /*定义递归参数
        必须传入结果集来进行结果的接受
        必须传入初始字符串来进行大小写的换
         */
        char[] chars = s.toCharArray();
        dfs(result, chars, 0);
        return result;
    }

    /**
     * @param result
     * @param chars
     * @param i
     */
    private void dfs(List<String> result, char[] chars, int i) {
        if (i == chars.length) {
            result.add(new String(chars));
            return;
        }
        if (Character.isLetter(chars[i])) {
            dfs(result, chars, i + 1);
            if (Character.isLetter(chars[i])) {
                chars[i] ^= 1 << 5;
                dfs(result, chars, i + 1);
            }
        }
    }

    public static void main(String[] args) {
        String question = "23";
//        char c = question.charAt(0);
//        System.out.println((char)'2');
//        System.out.println(question.charAt(0));
        letterCombinations(question);
    }

    /**
     * 给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。
     * 答案可以按 任意顺序 返回。
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * 2 = abc
     * 3 =edf
     * 4 =ghi
     * 5 =jkl
     * 6 =mno
     * 7 =pqrs
     * 8 = tuv
     * 9= wxyz
     */
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0) return result;
        String[] phone = {
                "abc",
                "edf",
                "ghi",
                "jkl",
                "mno",
                "pqrs",
                "tuv",
                "wxyz"};
        System.out.println(phone.length);
        StringBuilder builder = new StringBuilder();
        dfs2(phone, digits, 0, result,builder);
        return result;
    }

    public static void dfs2(String[] phone, String digits, int index, List<String> result,StringBuilder builder) {
        if (index == digits.length()) {
            //找到一个
            result.add(builder.toString());
            return;
        }
        String var = phone[digits.charAt(index)-'2'];
        char[] chars = var.toCharArray();
        for (char aChar : chars) {
            builder.append(aChar);
            //回溯
            dfs2(phone,digits,index+1,result,builder);
            //撤销
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}
